package 栈与队列;

import java.util.HashMap;
import java.util.Map;

/**
 * 105. 从前序与中序遍历序列构造二叉树
 *
 * 给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。
 *
 * 思路：
 *  前序遍历：根节点 -> 左子树 -> 右子树
 *  中序遍历：左子树 -> 根节点 -> 右子树
 *  因此，可以先根据前序遍历的第一个节点，在中序遍历中找到其位置，然后递归地构造左右子树。
 *
 * 解题步骤：
 * 1： 预处理：使用哈希表记录中序遍历的索引，快速定位根节点的位置。
 * 2：递归构建：
 *  终止条件：当数组为空时，返回 null。
 *  根节点：前序遍历中的第一个元素是当前子树的根；
 *  分割左右子树：根据中序遍历的根节点位置，确认左右子树的区间；
 * 3：索引计算：通过中序分割的左右子树长度，确认前序遍历的左右子树区间；
 *
 */
public class L_105 {

    private Map<Integer, Integer> inorderIndexMap; // 中序遍历索引哈希表
    private int[] preorder; // 前序遍历数组

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        this.preorder = preorder;
        inorderIndexMap = new HashMap<>();
        for (int i = 0; i < inorder.length; i++) {
            inorderIndexMap.put(inorder[i], i);
        }
        return build(0,preorder.length-1,0,inorder.length-1);
    }

    // 递归构建
    private TreeNode build(int preStart,int preEnd,int inStart,int inEnd){
        // 递归终止条件
        if(preStart > preEnd || inStart > inEnd){
            return null;
        }
        // 获取根节点, 前序遍历的第一个元素是当前子树的根
        int rootVal = preorder[preStart];
        TreeNode root = new TreeNode(rootVal);

        // 在中序遍历中找到根节点的位置
        int rootIndex = inorderIndexMap.get(rootVal);

        // 计算左子树的长度
        int leftSize = rootIndex - inStart;

        // 递归构建左子树
        root.left = build(
                preStart+1, // 左子树在前序中的起始位置
                preStart+leftSize, // 左子树在前序中的结束位置
                 inStart, // 左子树在中序中的起始位置
                rootIndex-1); // 左子树在中序中的结束位置
        // 递归构建右子树
        root.right = build(
                preStart+leftSize+1, // 右子树在前序中的起始位置
                preEnd,// 右子树在前序中的结束位置
                rootIndex+1,// 右子树在中序中的起始位置
                inEnd);// 右子树在中序中的结束位置
        return root;
    }

    public class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode() {}
      TreeNode(int val) { this.val = val; }
      TreeNode(int val, TreeNode left, TreeNode right) {
          this.val = val;
          this.left = left;
          this.right = right;
      }
  }
}
